#pragma once 
#include <iostream>
#include <vector>
#include <string>
#include <bitset>
using namespace std;

struct BKDRHash
{
	size_t operator()(const string& s)
	{
		// BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};

struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (size_t i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};


template<size_t N, size_t X,
  class HashFunc1,
  class HashFunc2,
  class HashFunc3>
class bloon_filter
{
  public:
    bloon_filter& set(const string&  str)
    {
      HashFunc1 h1;
      HashFunc2 h2;
      HashFunc3 h3;
      size_t len = X * N;
      size_t index1 = h1(str) % len;
      size_t index2 = h2(str) % len;
      size_t index3 = h3(str) % len;
      bs.set(index1);
      bs.set(index2);
      bs.set(index3);
      //cout << index1 << endl;
      //cout << index2 << endl;
      //cout << index3 << endl;
      return *this;
    }

    bool test(const string& str)
    {
      HashFunc1 h1;
      HashFunc2 h2;
      HashFunc3 h3;
      size_t len = X * N;
      size_t index1 = h1(str) % len;
      size_t index2 = h2(str) % len;
      size_t index3 = h3(str) % len;
      return bs.test(index1) 
        &&   bs.test(index2)
        &&   bs.test(index3);
    }
  private:
    bitset<N * X> bs;
};
